<?php
include 'Node.php';
class LinkedList
{
    private $head;
    private $size;

    public function __construct() {
        $this->head = null;
        $this->size = 0;
    }

    public function size() {
        return $this->size;
    }

    public function isEmpty() {
        return $this->size === 0;
    }

    public function add($element) {
        $newNode = new Node($element);
        if ($this->isEmpty()) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
        $this->size++;
    }

    public function remove($index) {
        if ($index < 0 || $index >= $this->size) {
            return false;
        }

        if ($index === 0) {
            $this->head = $this->head->next;
        } else {
            $current = $this->head;
            $prev = null;

            for ($i = 0; $i < $index; $i++) {
                $prev = $current;
                $current = $current->next;
            }

            $prev->next = $current->next;
        }

        $this->size--;
        return true;
    }

    public function get($index) {
        if ($index < 0 || $index >= $this->size) {
            return null;
        }

        $current = $this->head;
        for ($i = 0; $i < $index; $i++) {
            $current = $current->next;
        }

        return $current->data;
    }

    public function addFirst($element) {
        $newNode = new Node($element);
        $newNode->next = $this->head;
        $this->head = $newNode;
        $this->size++;
    }

    public function addLast($element) {
        $this->add($element);
    }

    public function removeFirst() {
        if ($this->isEmpty()) {
            return null;
        }

        $data = $this->head->data;
        $this->head = $this->head->next;
        $this->size--;

        return $data;
    }

    public function removeLast() {
        if ($this->isEmpty()) {
            return null;
        }

        $current = $this->head;
        $prev = null;

        while ($current->next !== null) {
            $prev = $current;
            $current = $current->next;
        }

        $data = $current->data;

        if ($prev === null) {
            // Only one element in the list
            $this->head = null;
        } else {
            $prev->next = null;
        }

        $this->size--;

        return $data;
    }

    public function indexOf($element) {
        $current = $this->head;
        $index = 0;

        while ($current !== null) {
            if ($current->data === $element) {
                return $index;
            }

            $current = $current->next;
            $index++;
        }

        return -1;
    }

    public function toArray() {
        $result = [];
        $current = $this->head;

        while ($current !== null) {
            $result[] = $current->data;
            $current = $current->next;
        }

        return $result;
    }

    public function clear() {
        $this->head = null;
        $this->size = 0;
    }
}
